#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  int get_min(int x, int y) {
    if (x < y) {
      return x;
    }
    return y;
  }
  int trap(vector<int> &height) {
    int length = height.size();

    vector<int> stack;

    int area = 0;
    for (int i = 0; i < length; i++) {

      while (!stack.empty() && height[i] > height[stack.back()]) {
        int top = stack.back();
        stack.pop_back();
        if (stack.empty()) {
          break;
        }
        int left = stack.back();
        int width = i - left - 1;
        int higth = get_min(height[i], height[left]) - height[top];

        area += width * higth;
      }

      stack.push_back(i);
    }

    return area;
  }
};

void testcase01() {
  printf("\n\n%s\n", __FUNCTION__);
  vector<int> input;
  input.push_back(4);
  input.push_back(2);
  input.push_back(0);
  input.push_back(3);
  input.push_back(2);
  input.push_back(5);

  Solution so;
  int got = so.trap(input);

  int expect = 9;

  if (got != expect) {
    printf("expect:%d, but got:%d\n", expect, got);
  }
}

void testcase02() {
  printf("\n\n%s\n", __FUNCTION__);
  vector<int> input;
  // 0,1,0,2,1,0,1,3,2,1,2,1
  input.push_back(0);
  input.push_back(1);
  input.push_back(0);
  input.push_back(2);
  input.push_back(1);
  input.push_back(0);
  input.push_back(1);
  input.push_back(3);
  input.push_back(2);
  input.push_back(1);
  input.push_back(2);
  input.push_back(1);

  Solution so;
  int got = so.trap(input);

  int expect = 6;

  if (got != expect) {
    printf("expect:%d, but got:%d\n", expect, got);
  }
}

int main() {
  testcase01();
  testcase02();
  return 0;
}
